package org.extremengine.collision;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * A graph data structure to store relationships between elements.
 * TODO full unit test.
 * @author yuxing
 *
 */
public class RelationGraph<E> {
	
	// Relation of two nodes in graph.
	private Set<Relation> relationSet = new HashSet<Relation>();
	
	// Map between target element and Node in graph.
	private Map<E, Node> nodeMap = new HashMap<E, Node>();
	
	// Relations to be removed which is added during traversing.
	Set<Relation> relationsToBeRemoved = new HashSet<Relation>();
	
	// Remove relation during traverse will cause ConcurrentModificationException, 
	// so use flag inTraverse to postpone remove operation.
	boolean inTraverse = false;

	public RelationGraph() {
	}
	
	
	/**
	 * Add element and all it's relations with all other element. 
	 * @param el
	 */
	public synchronized void addElement(E el) {
		// Relations to all other element except myself.
		Node node = new Node(el);
		nodeMap.put(el, node);
		for (Iterator it = nodeMap.values().iterator(); it.hasNext();) {
			Node n = (Node) it.next();
			if(el != n) {
				Relation r = new Relation(node, n);
				node.addRelation(r);
				relationSet.add(r);
			}
		}
	}

	
	/**
	 * Remove all relations of one element.
	 * @param removedEl
	 */
	public synchronized void removeRelation(E removedEl) {
		// Traverse all relations of this node and remove them from relations set.
		Node node1 = nodeMap.get(removedEl);
		List<Relation> realtions = node1.getRelations();
		for (int i = 0; i < realtions.size(); i++) {
			Relation curRelation = realtions.get(i);
			node1.getRelatedNode(curRelation).removeRelation(curRelation);
			if(inTraverse == true) {
				relationsToBeRemoved.add(curRelation);
			}
			else {
				relationSet.remove(curRelation);
			}
		}
		node1.getRelations().clear();
	}

	/**
	 * Remove one relation between e1 and e2.
	 * 
	 * @param e1
	 * @param e2
	 */
	public synchronized void removeRelation(E e1, E e2) {
		Node node = nodeMap.get(e1);
		List<Relation> relations = node.getRelations();
		for (int i = 0; i < relations.size(); i++) {
			if (relations.get(i).contains(e2)) {
				node.removeRelation(i);
				if (inTraverse == true) {
					relationsToBeRemoved.add(relations.get(i));
				}
				else {
					relationSet.remove(relations.get(i));
				}
				return;
			}
		}
	}
	
	/**
	 * Do removing if possible.
	 */
	private void doRemoving() {
		// Traverse all relations that marked to be removed.
		for (Iterator it = relationsToBeRemoved.iterator(); it.hasNext();) {
			Relation target = (Relation) it.next();
			relationSet.remove(target);
		}
		relationsToBeRemoved.clear();
	}
	
	/**
	 * Traverse all relations to do something which is defined in callback.
	 * It is safe that removing relations from graph during traverse, the real removing operation 
	 * will be delayed after traversing is done.
	 * @param callback
	 */
	public void traverseRelationSafe(TraverseCallback callback) {
		inTraverse = true; // Atomic
		for (Iterator it = relationSet.iterator(); it.hasNext();) {
			Relation entry = (Relation) it.next();
			callback.onEntry(entry);
		}
		inTraverse = false; // Atomic
		callback.onComplete();
	}

	@Override
	public String toString() {
		return "Elements: " + nodeMap.size() + ", Relations: " + relationSet.size();
	}

	
	/**
	 * 
	 * @author yuxing
	 *
	 */
	public static interface TraverseCallback {
		public void onEntry(Relation entry);
		public void onComplete();
	}
	
	
	/**
	 * 
	 * @author yuxing
	 *
	 * @param <E>
	 */
	public static class Node<E> {
		private E userObject;
		private List<Relation> relations = new ArrayList();
		
		public Node(E userObject) {
			super();
			this.userObject = userObject;
		}

		
		public E getUserObject() {
			return userObject;
		}


		public void setUserObject(E userObject) {
			this.userObject = userObject;
		}


		public void addRelation(Relation entry) {
			relations.add(entry);
		}
		
		public void removeRelation(int index) {
			relations.remove(index);
		}
		
		public void removeRelation(Relation entry) {
			relations.remove(entry);
		}

		public List<Relation> getRelations() {
			return relations;
		}
		
		public Node getRelatedNode(Relation relation) {
			if(relation.getNode1() == this.userObject){
				return relation.getNode2();
			}
			return relation.getNode1();
		}
	
	}
	
	/**
	 * Relation between two elements.
	 * @author yuxing
	 * 
	 */
	public static class Relation<E> {
		private Node<E> node1;
		private Node<E> node2;

		public Relation(Node<E> node1, Node<E> node2) {
			super();
			this.node1 = node1;
			this.node2 = node2;
		}

		public Node<E> getNode1() {
			return node1;
		}

		public void setNode1(Node<E> node1) {
			this.node1 = node1;
		}

		public Node<E> getNode2() {
			return node2;
		}

		public void setNode2(Node<E> node2) {
			this.node2 = node2;
		}
		
		public E getE1() {
			return node1.getUserObject();
		}
		
		public E getE2() {
			return node2.getUserObject();
		}

		public boolean contains(E e) {
			return node1.getUserObject() == e || node2.getUserObject() == e;
		}

		public boolean contains(E e1, E e2) {
			return (this.node1.getUserObject() == e1 && this.node2.getUserObject() == e2)
					|| (this.node1.getUserObject() == e2 && this.node2.getUserObject() == e1);
		}
	}

}
